package cn.kent.simple;

import java.util.*;

/**
 * 217. 存在重复元素
 * 存在重复的元素则返回true
 * 方法：
 * 1.哈希表
 * 2.排序 - 很慢
 */
public class ContainsDuplicate {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println(containsDuplicate4(nums));
        // Hashtable<Object, Object> hashtable = new Hashtable<>();
        // hashtable.put("1", 1);
        // hashtable.put("1", 2);
        // System.out.println(hashtable.get("1"));

    }

    /**
     * 哈希表
     */
    public static boolean containsDuplicate4(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num))
                return true;
        }
        return false;
    }


    /**
     * 排序
     */
    public static boolean containsDuplicate3(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] == nums[i]) {
                return true;
            }
        }
        return false;
    }

    /**
     * 两层循环 - 超时
     */
    public static boolean containsDuplicate2(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int j = i + 1;
            while (j < nums.length) {
                if (nums[i] == nums[j])
                    return true;
                j++;
            }
        }
        return false;
    }

    /**
     * 哈希表实现
     */
    public static boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.get(num) != null)
                return true;
            else
                map.put(num, num);
        }
        return false;
    }
}
